784
class Solution {
    ListString ret = new ArrayList();

    public ListString letterCasePermutation(String s) {
        fun(new StringBuilder(), s, 0, s.length());
        return ret;
    }

    public void fun(StringBuilder str, String s, int i, int len) {
        if (i == len) {
            ret.add(str.toString());
            return;
        }
        char c = s.charAt(i);
        str.append(c);
        fun(str, s, i+1, len);
        str.deleteCharAt(i);
        if (c = 'Z' && c = 'A') {
            str.append((char)(c+32));
            fun(str, s, i+1, len);
            str.deleteCharAt(i);
        } else if (c = 'z' && c = 'a') {
            str.append((char)(c-32));
            fun(str, s, i+1, len);
            str.deleteCharAt(i);
        }
    }
}
class Solution {
    public int countSegments(String s) {
        if (s == null || s.length() == 0 ){
            return 0;
        }


        int count = 0;
        for (int i = 0; i < s.length()-1; i++){
            if (s.charAt(i) != ' ' && s.charAt(i + 1) == ' '){
                count ++;
            }else if (i == s.length() - 2){
                if (s.charAt(i) != ' ' || s.charAt(i + 1) != ' '){
                    count++;
                }
            }
        }
        if (s.length() == 1 && s.charAt(0) != ' '){
            count++;
        }
        
        return count;
    }
}

链接：https://ac.nowcoder.com/acm/problem/50039
来源：牛客网

kotori最近迷上了摆气球的游戏。她一共有n种气球，每种气球有无数个。她要拿出若干个气球摆成一排。

但是，由于气球被施放了魔法，同样种类的气球如果相邻会发生爆炸，因此若两个相邻的气球种类相同被视为不合法的。

kotori想知道，摆成一排m个一共有多少种不同的方案？

由于该数可能过大，只需要输出其对109取模的结果
import java.util.Scanner;


public class Main{
    public static void main(String argu[]){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        long num = n;
        for (int i = 1; i < m; i++){
            num *= (n - 1);
            num %= 109;
        }
        System.out.println(num);
    }
}
